// 更高效的快速排序
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return;
  
  // 分区操作，返回基准值的最终位置
  const pivotIndex = partition(arr, left, right);
  
  // 递归排序基准值左边的子数组
  quickSortInPlace(arr, left, pivotIndex - 1);
  // 递归排序基准值右边的子数组
  quickSortInPlace(arr, pivotIndex + 1, right);
  
  return arr;
}

function partition(arr, left, right) {
  // 选择最右边的元素作为基准值
  const pivot = arr[right];
  let i = left;
  
  // 将小于基准值的元素移动到左侧
  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      // 交换元素
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  
  // 将基准值放到正确的位置
  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

// 示例用法
const array = [64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42];
console.log("原始数组:", array);
console.log("排序后数组:", quickSortInPlace(array));